package utils.course;

/**
 * 使用双向队列实现栈和队列
 */
public class DoubleEndsQueueToStackAndQueue {
    //构造一个双向链表
    public static class Node<T>{
        public T value;
        public Node<T> lastNode;
        public Node<T> nextNode;

        public Node(T value){
            this.value = value;
        }
    }
    public static class DoubleEndsQueue<T>{
        //头部，和尾部指针
        public Node head;
        public Node tail;

        // 从头部向队列中添加值
        public void addFromHead(T value){
            // 创建一个节点存储传进来的value
            Node cur = new Node(value);
            // 如果当前队列为空（没有节点）,则头，尾都指向这个新节点cur
            if (null==head){
                head = cur;
                tail = cur;
            }else {//节点不为空，往头部添加，head前移，尾部不动
                cur.nextNode = head;
                head.lastNode = cur;
                head = cur;
            }
        }
        // 从尾部向队列中添加值
        public void addFromBottom(T value){
            Node<T> cur = new Node(value);
            if (null==head){
                head = cur;
                tail = cur;
            }else {
                cur.lastNode = tail;
                tail.nextNode = cur;
                tail = cur;
            }
        }
        //从头部取值
        public T popFromHead(){
            if (null==head){
                return null;
            }
            Node<T> cur = head;
            // 头部和尾部指向同一个节点==>只有一个节点
            if (head == tail){
                head = null;
                tail = null;
            }else { // 有两个及以上节点
                head = head.nextNode;
                head.lastNode = null;
                cur.nextNode = null;
            }
            return cur.value;
        }
        //从尾部取值
        public T popFromBottom(){
            if (null==head){
                return null;
            }
            Node<T> cur = tail;
            // 只有一个元素
            if (head == tail){
                head = null;
                tail = null;
            }else { // 有两个及以上元素
                tail = tail.lastNode;
                tail.nextNode = null;
                cur.lastNode = null;
            }
            // 返回底部元素；
            return cur.value;
        }
        // 判断栈是否为空
        public boolean isEmpty(){
            return head == null;
        }


    }

    /**
     * 模拟栈
     * @param <T>
     */
    public static class Stack<T>{
        private DoubleEndsQueue<T> queue;
        public Stack(){
            queue = new DoubleEndsQueue<>();
        }
        public void push(T value){
            queue.addFromHead(value);
        }
        public T pop(){
            return queue.popFromHead();
        }
        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }

    /**
     * 模拟队列
     * @param <T>
     */
    public static class Queue<T>{
        // 初始化一个双向链表
        private DoubleEndsQueue<T> queue;
        public Queue(){
            queue = new DoubleEndsQueue<>();
        }
        public void push(T value){
            queue.addFromHead(value);
        }
        public T poll(){
           return queue.popFromBottom();
        }
        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }

/*    public static void main(String[] args) {
        Queue<Object> queue = new Queue<>();
        System.out.println("队列是空的吗？"+queue.isEmpty());
        for (int i = 0; i < 10; i++) {
            queue.push(i);
            System.out.print(i+",");
        }
        System.out.println("队列是空的吗？"+queue.isEmpty());
        System.out.println("=======");
        for (int i = 0; i < 10; i++) {
            System.out.print(queue.poll()+",");
        }
        System.out.println("队列是空的吗？"+queue.isEmpty());
    }*/

/*    public static void main(String[] args) {
        Stack<Object> stack = new Stack<>();
        System.out.println("栈是空的吗？"+stack.isEmpty());
        for (int i = 0; i < 12; i++) {
            stack.push(i);
            System.out.print(i+",");
        }
        System.out.println("栈是空的吗？"+stack.isEmpty());
        for (int i = 0; i < 12; i++) {
            System.out.print(stack.pop()+",");
        }
        System.out.println("栈是空的吗？"+stack.isEmpty());
    }*/
}
